class Solution {
public:
    int* Process(vector<int>& nums,int left,int right,int pivot)
    {
        int less = left;
        int more = right;
        int cur = left;
        while(cur <= more)
        {
            if(nums[cur] < pivot)
                ::swap(nums[less++],nums[cur++]);
            else if(nums[cur] > pivot)
                ::swap(nums[more--],nums[cur]);
            else
                cur++; 
        }
        //[left,less) (more,right]
        return new int[2]{less,more};
    }
    void QuickSort(vector<int>& nums,int left,int right)
    {
        if(left >= right) return ;
        //[left,right] right - left + 1
        ::swap(nums[right],nums[left + rand() % (right - left + 1)]);
        int* equal = Process(nums,left,right,nums[right]);
        //[left,equal[0]-1] [equal[1]+1,right]
        QuickSort(nums,left,equal[0]-1);
        QuickSort(nums,equal[1]+1,right);
    }
    vector<int> sortArray(vector<int>& nums) {
        QuickSort(nums,0,nums.size()-1);
        return nums;
    }
};


    void MergeSort(vector<int>& v,int left,int right,vector<int>& tmp)
    {
        if(left  >= right) return ;
        int mid = (left + right) >> 1;
        MergeSort(v,left,mid,tmp);
        MergeSort(v,mid+1,right,tmp);
        
        int begin1 = left,end1 = mid,begin2 = mid+1,end2 = right;
        int index = left;
        while(begin1 <= end1 && begin2 <= end2)
        {
            if(v[begin1] > v[begin2])
                tmp[index++] = v[begin2++];
            else 
                tmp[index++] = v[begin1++];
        }
        while(begin1 <= end1) tmp[index++] = v[begin1++];
        while(begin2 <= end2) tmp[index++] = v[begin2++];

        for(int i = left;i<=right;i++)
            v[i] = tmp[i];
    }
    vector<int> sortArray(vector<int>& nums) {
        vector<int> tmp(nums.size(),0);
        MergeSort(nums,0,nums.size()-1,tmp);
        return nums;
    }